import copy
from typing import List

import sys

sys.setrecursionlimit(10000)  # set the maximum depth as 10000


class Solution:
    def __init__(self):
        self.have_queue = []
    
    # def findOrderCore(self, course, prerequisites: dict, queuelist):
    #     course_list = prerequisites.get(course)
    #     if course_list != None:
    #         for value in course_list:
    #             if value in queuelist:
    #                 return True
    #             queuelist.append(course)
    #             if not value in self.have_queue:
    #                 self.have_queue.append(value)
    #             if self.findOrderCore(value, prerequisites, copy.copy(queuelist)):
    #                 return True
    #         return False
    #     else:
    #         self.have_queue = queuelist
    #         self.have_queue.append(course)
    #         return False
    #
    # def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    #     if len(prerequisites)==0:
    #         return [i for i in range(numCourses)]
    #     graph = {}
    #     for prerequisite in prerequisites:
    #         if graph.get(prerequisite[0]) is None:
    #             graph[prerequisite[0]] = []
    #         graph[prerequisite[0]].append(prerequisite[1])
    #
    #     for k, v in graph.items():
    #         if k in self.have_queue:
    #             continue
    #         if self.findOrderCore(k, graph, []):
    #             return []
    #     return self.have_queue
    
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = {}
        degrees = {}
        for i in range(numCourses):
            graph[i] = []
            degrees[i] = 0
        for prerequisite in prerequisites:
            graph[prerequisite[1]].append(prerequisite[0])
            degrees[prerequisite[0]] += 1
        
        queue = [u for u in graph if degrees[u] == 0]
        res = []
        while queue:
            u = queue.pop()
            res.append(u)
            for v in graph[u]:
                degrees[v] -= 1
                if degrees[v] == 0:
                    queue.append(v)
        # res.reverse()
        return res if len(res)==len(degrees) else []


def main():
    sol = Solution()
    print(sol.findOrder(3,
[[1,0],[1,2],[0,1]]))


if __name__ == "__main__":
    main()
